Tables

Topics: Toronto, Grey and Bruce Railway Company, Railroads, Chemins de fer

52
52

Jul 20, 2013
07/13

by
Torsten Inkmann; Robin Thomas

texts

######
eye 52

######
favorite 0

######
comment 0

Let k>0 be an integer, let H be a minor-minimal graph in the projective plane such that every homotopically non-trivial closed curve intersects H at least k times, and let G be the planar double cover of H obtained by lifting G into the universal covering space of the projective plane, the sphere. We prove that G is minor-minimal of branch-width 2k. We also exhibit examples of minor-minimal planar graphs of branch-width 6 that do not arise this way.

Source: http://arxiv.org/abs/1007.0373v2

2
2.0

Jun 29, 2018
06/18

by
Alexander Hoyer; Robin Thomas

texts

######
eye 2

######
favorite 0

######
comment 0

Gyori and Lovasz independently proved the following beautiful theorem. Let $k\ge2$ be an integer, let $G$ be a $k$-connected graph on $n$ vertices, let $v_1,v_2,\ldots,v_k$ be distinct vertices of $G$ and let $n_1,n_2,\ldots,n_k$ be positive integers with $n_1+n_2+\cdots+n_k=n$. Then $G$ has disjoint connected subgraphs $G_1,G_2,\ldots,G_k$ such that for $i=1,2,\ldots,k$ the graph $G_i$ has $n_i$ vertices and $v_i\in V(G_i)$. We give a self-contained exposition of Gyori's proof.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1605.01474

6
6.0

Jun 30, 2018
06/18

by
Sergey Norin; Robin Thomas

texts

######
eye 6

######
favorite 0

######
comment 0

Almost $4$-connectivity is a weakening of $4$-connectivity which allows for vertices of degree three. In this paper we prove the following theorem. Let $G$ be an almost $4$-connected triangle-free planar graph, and let $H$ be an almost $4$-connected non-planar graph such that $H$ has a subgraph isomorphic to a subdivision of $G$. Then there exists a graph $G'$ such that $G'$ is isomorphic to a minor of $H$, and either (i) $G'=G+uv$ for some vertices $u,v\in V(G)$ such that no facial cycle of...

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1402.1999

5
5.0

Jun 29, 2018
06/18

by
Luke Postle; Robin Thomas

texts

######
eye 5

######
favorite 0

######
comment 0

Let $G$ be a graph embedded in a fixed surface $\Sigma$ of genus $g$ and let $L=(L(v):v\in V(G))$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $G$ is triangle-free, or each list has size at least three and $G$ has no cycle of length four or less. An $L$-coloring of $G$ is a mapping $\phi$ with domain $V(G)$ such that $\phi(v)\in L(v)$ for every $v\in V(G)$ and $\phi(v)\ne\phi(u)$ for every pair of adjacent vertices $u,v\in...

Topics: Combinatorics, Discrete Mathematics, Computing Research Repository, Mathematics

Source: http://arxiv.org/abs/1609.06749

2
2.0

Jun 30, 2018
06/18

by
Zdenek Dvorak; Robin Thomas

texts

######
eye 2

######
favorite 0

######
comment 0

A graph H is t-apex if H-X is planar for some subset X of V(H) of size t. For any integer t>=0 and a fixed t-apex graph H, we give a polynomial-time algorithm to decide whether a (t+3)-connected H-minor-free graph is colorable from a given assignment of lists of size t+4. The connectivity requirement is the best possible in the sense that for every t>=1, there exists a t-apex graph H such that testing (t+4)-colorability of (t+2)-connected H-minor-free graphs is NP-complete. Similarly, the...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1401.1399

2
2.0

Jun 30, 2018
06/18

by
Rajneesh Hegde; Robin Thomas

texts

######
eye 2

######
favorite 0

######
comment 0

A graph G is weakly 4-connected if it is 3-connected, has at least five vertices, and for every pair of sets (A,B) with union V(G) and intersection of size three such that no edge has one end in A-B and the other in B-A, one of the induced subgraphs G[A], G[B] has at most four edges. We describe a set of constructions that starting from a weakly 4-connected planar graph G produce a finite list of non-planar weakly 4-connected graphs, each having a minor isomorphic to G, such that every...

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository

Source: http://arxiv.org/abs/1401.2973

3
3.0

Jun 29, 2018
06/18

by
Luke Postle; Robin Thomas

texts

######
eye 3

######
favorite 0

######
comment 0

Let $G$ be a plane graph with outer cycle $C$ and let $(L(v):v\in V(G))$ be a family of non-empty sets. By an $L$-coloring of $G$ we mean a (proper) coloring $\phi$ of $G$ such that $\phi(v)\in L(v)$ for every vertex $v$ of $G$. Thomassen proved that if $v_1,v_2\in V(C)$ are adjacent, $L(v_1)\ne L(v_2)$, $|L(v)|\ge3$ for every $v\in V(C)-\{v_1,v_2\}$ and $|L(v)|\ge5$ for every $v\in V(G)-V(C)$, then $G$ has an $L$-coloring. What happens when $v_1$ and $v_2$ are not adjacent? Then an...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1608.05759

44
44

Sep 23, 2013
09/13

by
Bertrand Guenin; Robin Thomas

texts

######
eye 44

######
favorite 0

######
comment 0

We give an "excluded minor" and a "structural" characterization of digraphs D that have the property that for every subdigraph H of D, the maximum number of disjoint circuits in H is equal to the minimum cardinality of a subset T of V(H) such that H\T is acyclic.

Source: http://arxiv.org/abs/1012.2749v1

5
5.0

Jun 30, 2018
06/18

by
Luke Postle; Robin Thomas

texts

######
eye 5

######
favorite 0

######
comment 0

Let G be a plane graph with outer cycle C, let u,v be vertices of C and let (L(x):x in V(G)) be a family of sets such that |L(u)|=|L(v)|=2, L(x) has at least three elements for every vertex x of C-{u,v} and L(x) has at least five elements for every vertex x of G-V(C). We prove a conjecture of Hutchinson that G has a (proper) coloring f such that f(x) belongs to L(x) for every vertex x of G. We will use this as a lemma in subsequent papers.

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository

Source: http://arxiv.org/abs/1402.1813

32
32

Sep 22, 2013
09/13

by
Asaf Shapira; Robin Thomas

texts

######
eye 32

######
favorite 0

######
comment 0

A graph G is k-critical if every proper subgraph of G is (k-1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least log n/(100log k), improving a bound of Alon, Krivelevich and Seymour from 2000. Examples of Gallai from 1963 show that the bound cannot be improved to exceed 2(k-1)log n/log(k-2). We thus settle the problem of bounding the minimal circumference of k-critical graphs, raised by Dirac in 1952 and Kelly and Kelly...

Source: http://arxiv.org/abs/0908.3169v2

8
8.0

Jun 27, 2018
06/18

by
Luke Postle; Robin Thomas

texts

######
eye 8

######
favorite 0

######
comment 0

Let $G$ be a plane graph with outer cycle $C$ and let $(L(v):v\in V(G))$ be a family of sets such that $|L(v)|\ge 5$ for every $v\in V(G)$. By an $L$-coloring of a subgraph $J$ of $G$ we mean a (proper) coloring $\phi$ of $J$ such that $\phi(v)\in L(v)$ for every vertex $v$ of $J$. We prove a conjecture of Dvorak et al. that if $H$ is a minimal subgraph of $G$ such that $C$ is a subgraph of $H$ and every $L$-coloring of $C$ that extends to an $L$-coloring of $H$ also extends to an $L$-coloring...

Topics: Combinatorics, Computing Research Repository, Mathematics, Discrete Mathematics

Source: http://arxiv.org/abs/1505.05927

35
35

Jul 20, 2013
07/13

by
Cristina G. Fernandes; Robin Thomas

texts

######
eye 35

######
favorite 0

######
comment 0

We give a simpler proof of Seymour's Theorem on edge-coloring series-parallel multigraphs and derive a linear-time algorithm to check whether a given series-parallel multigraph can be colored with a given number of colors.

Source: http://arxiv.org/abs/1107.5370v1

69
69

Sep 23, 2013
09/13

by
Zdenek Dvorak; Daniel Kral; Robin Thomas

texts

######
eye 69

######
favorite 0

######
comment 0

We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nesetril and Ossona de Mendez. This generalizes several results from the literature, because many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn...

Source: http://arxiv.org/abs/1109.5036v2

29
29

Sep 19, 2013
09/13

by
Neil Robertson; Paul Seymour; Robin Thomas

texts

######
eye 29

######
favorite 0

######
comment 0

We announce results about flat (linkless) embeddings of graphs in 3-space. A piecewise-linear embedding of a graph in 3-space is called {\it flat} if every circuit of the graph bounds a disk disjoint from the rest of the graph. We have shown: (i) An embedding is flat if and only if the fundamental group of the complement in 3-space of the embedding of every subgraph is free. (ii) If two flat embeddings of the same graph are not ambient isotopic, then they differ on a subdivision of $K_5$ or...

Source: http://arxiv.org/abs/math/9301216v1

32
32

Sep 22, 2013
09/13

by
Zdenek Dvorak; Daniel Kral; Robin Thomas

texts

######
eye 32

######
favorite 0

######
comment 0

Let G be a plane graph of girth at least five. We show that if there exists a 3-coloring phi of a cycle C of G that does not extend to a 3-coloring of G, then G has a subgraph H on O(|C|) vertices that also has no 3-coloring extending phi. This is asymptotically best possible and improves a previous bound of Thomassen. In the next paper of the series we will use this result and the attendant theory to prove a generalization to graphs on surfaces with several precolored cycles.

Source: http://arxiv.org/abs/1302.2158v2

34
34

Sep 20, 2013
09/13

by
Ken-ichi Kawarabayashi; Robin Thomas; Paul Wollan

texts

######
eye 34

######
favorite 0

######
comment 0

We give an elementary and self-contained proof, and a numerical improvement, of a weaker form of the excluded clique minor theorem of Robertson and Seymour, the following. Let t,r>0 be integers, and let R=49152t^{24}(40t^2+r). An r-wall is obtained from a (2r x r)-grid by deleting every odd vertical edge in every odd row and every even vertical edge in every even row, then deleting the two resulting vertices of degree one, and finally subdividing edges arbitrarily. The vertices of degree two...

Source: http://arxiv.org/abs/1207.6927v2

26
26

Sep 19, 2013
09/13

by
Neil Robertson; P. D. Seymour; Robin Thomas

texts

######
eye 26

######
favorite 0

######
comment 0

Given a 0-1 square matrix A, when can some of the 1's be changed to -1's in such a way that the permanent of A equals the determinant of the modified matrix? When does a real square matrix have the property that every real matrix with the same sign pattern (that is, the corresponding entries either have the same sign or are both zero) is nonsingular? When is a hypergraph with n vertices and n hyperedges minimally nonbipartite? When does a bipartite graph have a "Pfaffian orientation"?...

Source: http://arxiv.org/abs/math/9911268v1

5
5.0

Jun 30, 2018
06/18

by
Neil Robertson; Paul Seymour; Robin Thomas

texts

######
eye 5

######
favorite 0

######
comment 0

We prove that every 3-regular graph with no circuit of length less than six has a subgraph isomorphic to a subdivision of the Petersen graph.

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository

Source: http://arxiv.org/abs/1405.0533

3
3.0

Jun 30, 2018
06/18

by
Zdenek Dvorak; Daniel Kral; Robin Thomas

texts

######
eye 3

######
favorite 0

######
comment 0

Let G be a 4-critical graph with t triangles, embedded in a surface of genus g. Let c be the number of 4-cycles in G that do not bound a 2-cell face. We prove that the sum of lengths of (>=5)-faces of G is at most linear in g+t+c-1.

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1404.6356

37
37

Sep 19, 2013
09/13

by
Zdenek Dvorak; Dan Kral; Robin Thomas

texts

######
eye 37

######
favorite 0

######
comment 0

Let G be a plane graph with exactly one triangle T and all other cycles of length at least 5, and let C be a facial cycle of G of length at most six. We prove that a 3-coloring of C does not extend to a 3-coloring of G if and only if C has length exactly six and there is a color x such that either G has an edge joining two vertices of C colored x, or T is disjoint from C and every vertex of T is adjacent to a vertex of C colored x. This is a lemma to be used in a future paper of this series.

Source: http://arxiv.org/abs/1010.2472v2

4
4.0

Jun 28, 2018
06/18

by
Zdenek Dvorak; Daniel Kral; Robin Thomas

texts

######
eye 4

######
favorite 0

######
comment 0

We give a linear-time algorithm to decide 3-colorability (and find a 3-coloring, if it exists) of quadrangulations of a fixed surface. The algorithm also allows to prescribe the coloring for a bounded number of vertices.

Topics: Combinatorics, Computing Research Repository, Mathematics, Discrete Mathematics

Source: http://arxiv.org/abs/1509.01013

6
6.0

Jun 30, 2018
06/18

by
Neil Robertson; Paul Seymour; Robin Thomas

texts

######
eye 6

######
favorite 0

######
comment 0

Let G be a cubic graph, with girth at least five, such that for every partition X,Y of its vertex set with |X|,|Y|>6 there are at least six edges between X and Y. We prove that if there is no homeomorphic embedding of the Petersen graph in G, and G is not one particular 20-vertex graph, then either G\v is planar for some vertex v, or G can be drawn with crossings in the plane, but with only two crossings, both on the infinite region. We also prove several other theorems of the same kind.

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1403.2118

6
6.0

Jun 29, 2018
06/18

by
Zdenek Dvorak; Daniel Kral; Robin Thomas

texts

######
eye 6

######
favorite 0

######
comment 0

We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmative case. The algorithms also allow to prescribe the coloring for a bounded number of vertices.

Topics: Discrete Mathematics, Combinatorics, Computing Research Repository, Mathematics

Source: http://arxiv.org/abs/1601.01197

98
98

Sep 17, 2012
09/12

by
Naylor, R. T. (Robin Thomas), 1945-

texts

######
eye 98

######
favorite 0

######
comment 0

Originally published, London , Unwin Hyman, 1987

Topics: Debts, External, Developing countries Governments External debts

3
3.0

Jun 30, 2018
06/18

by
Zdeněk Dvořák; Daniel Kráľ; Robin Thomas

texts

######
eye 3

######
favorite 0

######
comment 0

We show that the size of a 4-critical graph of girth at least five is bounded by a linear function of its genus. This strengthens the previous bound on the size of such graphs given by Thomassen. It also serves as the basic case for the description of the structure of 4-critical triangle-free graphs embedded in a fixed surface, presented in a future paper of this series.

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1402.4710

50
50

Jan 26, 2012
01/12

by
Naylor, R. T. (Robin Thomas), 1945-

texts

######
eye 50

######
favorite 0

######
comment 0

35
35

Sep 22, 2013
09/13

by
Zdenek Dvorak; Ken-ichi Kawarabayashi; Robin Thomas

texts

######
eye 35

######
favorite 0

######
comment 0

Grotzsch's theorem states that every triangle-free planar graph is 3-colorable. Several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an O(n log n) algorithm). We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph....

Source: http://arxiv.org/abs/1302.5121v1

13
13

Jun 27, 2018
06/18

by
Neil Robertson; P. D. Seymour; Robin Thomas

texts

######
eye 13

######
favorite 0

######
comment 0

A cubic graph $G$ is cyclically 5-connected if $G$ is simple, 3-connected, has at least 10 vertices and for every set $F$ of edges of size at most four, at most one component of $G\backslash F$ contains circuits. We prove that if $G$ and $H$ are cyclically 5-connected cubic graphs and $H$ topologically contains $G$, then either $G$ and $H$ are isomorphic, or (modulo well-described exceptions) there exists a cyclically 5-connected cubic graph $G'$ such that $H$ topologically contains $G'$ and...

Topics: Combinatorics, Computing Research Repository, Discrete Mathematics, Mathematics

Source: http://arxiv.org/abs/1503.02298

66
66

Jul 20, 2013
07/13

by
Ken-ichi Kawarabayashi; Serguei Norine; Robin Thomas; Paul Wollan

texts

######
eye 66

######
favorite 0

######
comment 0

We prove that every sufficiently big 6-connected graph of bounded tree-width either has a K_6 minor, or has a vertex whose deletion makes the graph planar. This is a step toward proving that the same conclusion holds for all sufficiently big 6-connected graphs. Jorgensen conjectured that it holds for all 6-connected graphs.

Source: http://arxiv.org/abs/1203.2171v2

4
4.0

Jun 30, 2018
06/18

by
Katherine Edwards; Daniel P. Sanders; Paul Seymour; Robin Thomas

texts

######
eye 4

######
favorite 0

######
comment 0

A graph is apex if there is a vertex whose deletion makes the graph planar, and doublecross if it can be drawn in the plane with only two crossings, both incident with the infinite region in the natural sense. In 1966, Tutte conjectured that every two-edge-connected cubic graph with no Petersen graph minor is three-edge-colourable. With Neil Robertson, two of us showed that this is true in general if it is true for apex graphs and doublecross graphs. In another paper, two of us solved the apex...

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1411.4352

43
43

Sep 18, 2013
09/13

by
Maria Chudnovsky; Neil Robertson; Paul Seymour; Robin Thomas

texts

######
eye 43

######
favorite 0

######
comment 0

A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge if no induced subgraph of G is an odd cycle of length at least 5 or the complement of one. The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic -- that every Berge graph either falls into one of a few...

Source: http://arxiv.org/abs/math/0212070v1

31
31

Sep 17, 2013
09/13

by
Guoli Ding; Bogdan Oporowski; Robin Thomas; Dirk Vertigan

texts

######
eye 31

######
favorite 0

######
comment 0

We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K_{4,k}, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax...

Source: http://arxiv.org/abs/0912.4778v2

2
2.0

Jun 30, 2018
06/18

by
Neil Robertson; Daniel P. Sanders; Paul Seymour; Robin Thomas

texts

######
eye 2

######
favorite 0

######
comment 0

In [J. Combin. Theory Ser. B 70 (1997), 2-44] we gave a simplified proof of the Four-Color Theorem. The proof is computer-assisted in the sense that for two lemmas in the article we did not give proofs, and instead asserted that we have verified those statements using a computer. Here we give additional details for one of those lemmas, and we include the original computer programs and data as "ancillary files" accompanying this submission.

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository

Source: http://arxiv.org/abs/1401.6481

5
5.0

Jun 30, 2018
06/18

by
Neil Robertson; Daniel P. Sanders; Paul Seymour; Robin Thomas

texts

######
eye 5

######
favorite 0

######
comment 0

In [J. Combin. Theory Ser. B 70 (1997), 2-44] we gave a simplified proof of the Four-Color Theorem. The proof is computer-assisted in the sense that for two lemmas in the article we did not give proofs, and instead asserted that we have verified those statements using a computer. Here we give additional details for one of those lemmas, and we include the original computer programs and data as "ancillary files" accompanying this submission.

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository

Source: http://arxiv.org/abs/1401.6485

78
78

Jul 20, 2013
07/13

by
Arash Asadi; Zdenek Dvorak; Luke Postle; Robin Thomas

texts

######
eye 78

######
favorite 0

######
comment 0

Thomassen conjectured that every triangle-free planar graph on n vertices has exponentially many 3-colorings, and proved that it has at least 2^[n^(1/12)/20000] distinct 3-colorings. We show that it has at least 2^sqrt(n/362) distinct 3-colorings.

Source: http://arxiv.org/abs/1007.1430v2

41
41

Jul 20, 2013
07/13

by
Ken-ichi Kawarabayashi; Serguei Norine; Robin Thomas; Paul Wollan

texts

######
eye 41

######
favorite 0

######
comment 0

Jorgensen conjectured that every 6-connected graph with no K_6 minor has a vertex whose deletion makes the graph planar. We prove the conjecture for all sufficiently large graphs.

Source: http://arxiv.org/abs/1203.2192v1

4
4.0

Jun 28, 2018
06/18

by
Thor Johnson; Neil Robertson; Paul Seymour; Robin Thomas

texts

######
eye 4

######
favorite 0

######
comment 0

In [Directed tree-width, J. Combin. Theory Ser. B 82 (2001), 138-154] we introduced the notion of tree-width of directed graphs and presented a conjecture, formulated during discussions with Noga Alon and Bruce Reed, stating that a digraph of huge tree-width has a large "cylindrical grid" minor. Here we prove the conjecture for planar digraphs, but many steps of the proof work in general. This is an unedited and unpolished manuscript from October 2001. Since many people asked for...

Topics: Combinatorics, Discrete Mathematics, Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1510.00473

38
38

Sep 18, 2013
09/13

by
Nathan Chenette; Luke Postle; Noah Streib; Robin Thomas; Carl Yerger

texts

######
eye 38

######
favorite 0

######
comment 0

We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no subgraph isomorphic to a member of the list.

Source: http://arxiv.org/abs/1201.5361v1

Publication statement from colophon

Topics: Jesuits, Grace de Dieu (Ship), Imprint 1613

50
50

Jan 10, 2012
01/12

by
Myer, Charles M; Cotton, Robin T. (Robin Thomas), 1941-

texts

######
eye 50

######
favorite 0

######
comment 0

Includes bibliographies and index

Topics: Pediatric otolaryngology, Otorhinolaryngologic Diseases

38
38

Sep 22, 2013
09/13

by
Deborah E. Berg; Serguei Norine; Francis Edward Su; Robin Thomas; Paul Wollan

texts

######
eye 38

######
favorite 0

######
comment 0

When can a majority of voters find common ground, that is, a position they all agree upon? How does the shape of the political spectrum influence the outcome? When mathematical objects have a social interpretation, the associated theorems have social applications. In this article we give examples of situations where sets model preferences and develop extensions of classical theorems about convex sets, such as Helly's theorem, that can be used in the analysis of voting in "agreeable"...

Source: http://arxiv.org/abs/0811.3245v1